package DataStructure.tree;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * 111. 二叉树的最小深度 https://leetcode.cn/problems/minimum-depth-of-binary-tree/
 * 题目简述：给定一个二叉树，找出其最小深度。
 */
public class MinDepth {

    /**
     * 思路一：递归法，树的最小深度为左右子树中的最小深度+1
     * 注意，若不存在一边子树，则树的最短路径为另一边子树最短路径+1。因为路径要到达叶子节点
     */
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int leftMinDepth = minDepth(root.left);
        int rightMinDepth = minDepth(root.right);
        return root.left == null || root.right == null ? leftMinDepth+rightMinDepth+1 : Math.min(leftMinDepth, rightMinDepth)+1;
    }

    /**
     * 思路二：找最短路径就是找最浅叶子结点的高度，可通过层序遍历从上到下一层一层扫描寻找叶子节点
     * 初始化时在队列中初始化第一层元素
     * 在一次循环中出队一层元素，每出队一个元素，则检查其是否为叶子节点，若为叶子节点，则直接返回当前高度h，若不是，则将其孩子节点入队。一层扫描结束后队列中即为下一层中的所有节点，进入下一次循环
     */
    public int minDepth2(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int h = 1;
        while (!queue.isEmpty()) {
            int ln = queue.size();
            for (int i = 1; i <= ln;i++) {
                TreeNode node = queue.remove();
                if (node.left == null && node.right == null) {
                    return h;
                }
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            h++;
        }
        return h;
    }

    /**
     * 思路三：非递归后序遍历解法
     */
    public int minDepth3(TreeNode root) {
        int minDepth = 0, depth = 0;
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                depth++;
                root = root.left;
            }
            if (stack.peek().right == null) {
                root = stack.pop();
                if (root.left == null && root.right == null) {
                    if (minDepth == 0) minDepth = depth;
                    if (depth < minDepth) minDepth = depth;
                }
                depth--;
                while (!stack.isEmpty() && stack.peek().right == root) {
                    root = stack.pop();
                    if (root.left == null && root.right == null) {
                        if (minDepth == 0) minDepth = depth;
                        if (depth < minDepth) minDepth = depth;
                    }
                    depth--;
                }
            }
            root = !stack.isEmpty() ? stack.peek().right : null;
        }
        return minDepth;
    }
}
